package offer2

/**
原题链接:
https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

B站 舞年落梦
剑指 Offer 13. 机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），
也不能进入行坐标和列坐标的数位之和大于k的格子。

例如，当k为18时，机器人能够进入方格 [35, 37] ，
因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：
输入：m = 2, n = 3, k = 1
输出：3
*/

// threshold: 数位之和限制  rows:行数  cols:列数
func movingCount(threshold int, rows int, cols int) int {
	if threshold < 0 || rows <= 0 || cols <= 0 { //只要有有个参数为0,即可返回0
		return 0
	}

	isVisited := make([][]bool, rows) //初始化遍历记录数组
	for i := 0; i < rows; i++ {       //
		isVisited[i] = make([]bool, cols)
	}
	return dfs(threshold, rows, cols, 0, 0, isVisited)
}

func dfs(threshold int, rows int, cols int, x int, y int, isVisited [][]bool) int {
	if x < 0 || y < 0 || x >= rows || y >= cols || isVisited[x][y] || digitalSum(x)+digitalSum(y) > threshold {
		return 0
	}
	isVisited[x][y] = true
	return 1 + dfs(threshold, rows, cols, x-1, y, isVisited) +
		dfs(threshold, rows, cols, x+1, y, isVisited) +
		dfs(threshold, rows, cols, x, y-1, isVisited) +
		dfs(threshold, rows, cols, x, y+1, isVisited)
}

func digitalSum(num int) int {
	var sum int
	for num > 0 {
		sum += num % 10
		num /= 10
	}
	return sum
}
